package mine.personal.demo.pratice.algorithm.sumofprefix;

import java.util.HashMap;
import java.util.Scanner;

/**
 * @Author: lhl
 * @CreateTime: 2025-03-24
 * @Description: 前缀和算法合集
 * @Version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {1,7,3,6,5,6};
        pivotIndex(nums);
    }

    /**
     * @author: 李鸿麟
     * @date: 2025/3/24
     * @param:
     * @throws
     * @return: void
     * 前缀和模板1
     */
    /**
        这个题我觉得还是很好的 虽然很简单但是很好的体现了“前缀和”的思想
        如果从题目一步步分析 其实发现暴力解法在单趟的时间复杂度也还可以 我觉得最可能的原因是 -> 数组可以随机存取
        但是暴力解法在这道题里行不通 因为要处理的输入和输出轮数太多 在最坏情况下就会超时
        而前缀和的解法在本质上我觉得和编口诀类似 用空间换时间的思路 建立一个辅助数组存储前n位的和 这样就可以减少遍历的次数
        为什么能够减少遍历次数呢 假设我现在需要求出3、4、5位的和是多少 只需要使用前5位的和-前2位的和就能得到 这点数学思路上的转换我觉得对于此题也是非常关键的
     */
    private static void prefixModule1() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), q = in.nextInt();
        long[] arr = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        // 最关键的一步:准备前缀和数组
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + arr[i];
        }
        while (q > 0) {
            int left = in.nextInt(), right = in.nextInt();
            //数学转换 我觉得非常妙
            System.out.println(dp[right] - dp[left - 1]);
            q--;
        }
    }

    /**
     * @author: 李鸿麟
     * @date: 2025/3/25
     * @param: none
     * @return: void
     * 牛客 【模板】二维前缀和
     */
    private static void prefixModule2() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        int[][] arr = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        // 最关键的一步:准备前缀和矩阵
        long [][] dp = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
            }
        }

        while (q > 0) {
            int x1 = in.nextInt(), y1 = in.nextInt();
            int x2 = in.nextInt(), y2 = in.nextInt();
            //数学转换 我觉得非常妙
            System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
            q--;
        }
    }

    /**
     * leetcode LCR012->寻找数组的中心下标
     * @author: 李鸿麟
     * @date: 2025/3/26
     * @param: nums
     * @return: int
     */
    public static int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        int[] suf = new int[n];
        pre[0] = 0; suf[n-1] = 0;
        int left = 1, right = n-2;
        for (int i = 0; i < n - 1; i++) {
            pre[left] = pre[left - 1] + nums[left - 1];
            suf[right] = suf[right + 1] + nums[right + 1];
            left++;
            right--;
        }
        for (int i = 0; i < n; i++) {
            if (pre[i] == suf[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * leetcode 238 除了自身以外的乘积
     * @author: 李鸿麟
     * @date: 2025/3/28
     * @param: nums
     * @return: int
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        int[] suf = new int[n];
        int[] ret = new int[n];
        pre[0] = 1; suf[n-1] = 1;
        int left = 1, right = n-2;
        for (int i = 0; i < n - 1; i++) {
            pre[left] = pre[left - 1] * nums[left - 1];
            suf[right] = suf[right + 1] * nums[right + 1];
            left++;
            right--;
        }
        for (int i = 0; i < n; i++) {
           ret[i] = pre[i]*suf[i];
        }
        return ret;
    }

    /**
     * leetcode LCR010 -> 和为k的子数组的数目
     * @author: 李鸿麟
     * @date: 2025/3/31
     * @param: nums
     * @param: k
     * @return: int
     */
    public int subarraySum(int[] nums, int k) {
        // 为什么要用哈希表 这个要从算法一开始的分析开始
        // 从这道题的暴力解法可以看出 我只需要暴力遍历出每个子数组的和 然后和k比较其实可以了 此时的算法的时间复杂度是O(n^2)
        // 但是这样是肯定会超时的 所以需要狠狠地优化
        // 但是双指针的优化思路行不通 因为数字有正有负 没办法保证窗口里的内容是一直单调的 如果按照双指针的思路 会遗漏
        // 于是在这里我们先引入一个新的概念 叫做i位置前的所有子数组 其实也就是末尾位置为i 起始位置依次从0递增到i-1的数组 (在这道题中 相当于固定末尾位置 找起始位置)
        // 有了这个概念 我们就可以使用前缀和的思路来解决这道题 怎么解决呢 需要用一下数学的转换思路 现在我需要求和为k的子数组有多少个
        // 然后前缀和可以告诉我i位置前的所有数组元素的和为多少(记为sum) 那么如果我能统计出i位置前所有元素和为sum-k的子数组的个数 那么其实就相当于统计出了和为k的子数组的个数
        // 有了这个转换思路 我们顺利过渡到了使用前缀和的思路来解决这道题 但是为什么要使用哈希表的问题还没有进行说明
        // 现在我们的核心问题是统计出i位置前所有元素和为sum-k的子数组的个数 如果用暴力思路求解 其实还是双循环遍历 但是这样求那我还不如一开始就暴力遍历呢
        // 所以我需要一种独特的数据结构 可以快速在一大批数字中找到一个独特的数字 并且能返回相应的结果 那么哈希表在合适不过了
        // 所以哈希表的设计可以推断出来 -> key为i位置前所有位置的前缀和 value是和出现的次数
        // 而在对nums数组的一次遍历中 首先计算前缀和 然后判断i位置前是否有其他位置的前缀和等于sum - k 如果有的话 让返回值+=出现过的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        // 魔鬼细节1. 这个细节在于处理整个数组的元素和正好是k的情况 在此情况下 需要返回1
        map.put(0, 1);
        int pre = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            // 魔鬼细节2 这道题不需要真的去模拟前缀和数组 如果真的模拟了 时间复杂度还不如直接暴力解
            pre += nums[i];
            ret += map.getOrDefault(pre - k, 0);
            // 魔鬼细节3 这道题我们找的是i位置前的所有子数组 所以当下标是i的时候，只找[0,i-1]位置的前缀和
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }

        return ret;
    }

    /**
     * leetcode 974 -> 和可以被k整除的子数组个数
     * @author: 李鸿麟
     * @date: 2025/4/1
     * @param: nums
     * @param: k
     * @return: int
     */
    public int subarraysDivByK(int[] nums, int k) {
        // 这个题和上个题很相似 只不过需要额外引入新的数学工具和java中对于负数余数的修正机制
        // 第一个需要引入的知识是同余定理 即(a - b) % m = 0 => a % m = b % m 定理在这里不予证明
        // 为什么要引入同余定理 因为在将这道题转换为前缀和问题的时候需要使用同余定理
        // 如果i位置的前缀和为sum i位置前的某一个子数组(起始位置为m)的元素和可被k整除 设i位置的前缀和为sum m位置的前缀和为x 则有以下式子
        // (sum - x) % k == 0 由同余定理可知 sum % k == x % k 这样就可以套用上一题的思路了
        // 也就是说 我只需要找到以0位置为开头 [0-i]位置为结尾的子数组 只要子数组的元素和同k的余数 == sum % k就行
        // 话又说回来 这道题还有一个很头疼的点 sum可以是负数 而在编程语言中 负数的存储一直是大家比较头疼的问题 如果这道题不负数的取模运算做出统一规定 就会出现情况遗漏的问题
        // 在数学运算中 -7 % 5 = 2 但是在java中 -7 % 5 = -2 这不符合数学运算规律 但是在整除运算中 -7 和 7 都可以被7整除 为了避免因为符号问题导致的情况丢失 我们就需要对于负数取余运算进行统一规定
        // 所以 通过同余定理 我们可以得知 无论sum是正数还是负数 通过(sum % k + k) % k 最后算出来的余数都是一个非负整数

        HashMap<Integer, Integer> map = new HashMap<>();
        // 魔鬼细节1. 这个细节在于处理整个数组的元素和正好可以被k整除的情况 在此情况下 需要返回1
        map.put(0, 1);
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            // 魔鬼细节2 这道题不需要真的去模拟前缀和数组 如果真的模拟了 时间复杂度还不如直接暴力解
            sum += nums[i];
            int r = (sum % k + k) % k;
            ret += map.getOrDefault(r , 0);
            // 魔鬼细节3 这道题我们找的是i位置前的所有子数组的前缀和余数 所以当下标是i的时候，只找[0,i-1]位置的前缀和余数 找完了 再添加
            map.put(r, map.getOrDefault(r, 0) + 1);
        }

        return ret;
    }

    public int findMaxLength(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[i] = -1;
            }
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int pre = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if(map.containsKey(pre)){
                ret = Math.max(ret, i - map.get(pre));
            } else {
                map.put(pre, i);
            }
        }

        return ret;
    }

    /**
     * leetcode -> 矩阵区域和
     * @author: 李鸿麟
     * @date: 2025/4/4
     * @param: mat
     * @param: k
     * @return: int
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        // 处理前缀和矩阵
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }

        // 处理返回结果
        int[][] answer = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;
                answer[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
            }
        }

        return answer;
    }
}
